package sort;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdRandom;

class Quick extends SortExample{

    public static void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        //sort(a,0,a.length-1);
        quick3way(a, 0, a.length-1);

    }

    public static void sort(Comparable [] a,int lo,int hi) {
        if (lo>=hi) return;
        int j = partition(a, lo, hi);
        sort(a,lo,j-1);
        sort(a,j+1,hi);
        
    }

    //数组切分
    public static int partition(Comparable [] a,int lo, int hi) {
        int i =lo ,j = hi+1;
        Comparable v = a[lo];
        while(true)
        {
            while (less(a[++i],v)) if (i== hi) break;
            while (less(v,a[--j])) if (j== lo) break;
            if (i>=j) break;
            exch(a,i,j);
        }
        exch(a,lo,j);
        return j;
    }



    //三向切分
    public static void quick3way(Comparable[] a,int lo,int hi) {
        if(hi <= lo) return;
        int lt = lo,i = lo+1,gt = hi;
        Comparable v = a[lo];
        while(i<=gt)
        {
            int cmp = a[i].compareTo(v);
            if (cmp <0) exch(a,lt++,i++);
            else if(cmp >0) exch(a,i,gt--);
            else i++;

        }
        quick3way(a,lo,lt-1);
        quick3way(a,gt+1,hi);
        
    }

    public static void main(String[] args) {
        String[] a = In.readStrings();
       //String[] a = StdIn.readAllStrings();
       sort(a);
       assert isSorted(a);
       show(a);
   }
}